The present invention relates to content addressable memories used for high-speed packet classification and the like and in particular to a ternary content addressable memory system providing reduced power consumption.
Standard random access computer memory stores data at memory locations that may be individually accessed, for example for reading, by providing the memory with an address of the memory location. The memory responds to the identified address by providing a data element stored in the memory location of that address. Random access memory allows high-speed access to data when the storage address of the data is known; however, when data of a particular value must be located and the address is not known, random access memory requires a time-consuming search in which multiple memory locations must be addressed in turn, and the stored data read and tested against the desired value.
Content addressable memories (CAMs), in some respect, are the mirror counterpart of random access memory, allowing data to be located simply by knowing the desired data value. The CAM memory receives a desired data value and then returns one or more addresses (or the contents of those addresses) where the data is located. Such memories are termed associative memories and this type of search is termed an associative search herein.
A special class of CAM memories are ternary content addressable memories (TCAMs) which allow the desired data value to be specified with wildcard characters allowing for a ranges of data values to be returned where only the non-wildcard characters need to match.
TCAMs are used in high-performance network hardware such as routers to perform data packet classification. Such classifications are often concerned with ranges of data values which the wildcard feature facilitates.
Packet classification is used in a variety of services, including not only standard routing of network packet data among nodes but also providing varied quality of service for different packets (QoS), performing packet filtering for security devices such as firewalls and malware detection systems (for example, denying all packets from a known source), implementing policy routing (for example, routing all voice over IP (VOIP) traffic over a separate network), and providing traffic shaping (for example, ensuring that no one source overloads the network).
TCAMs when used to classify network data may receive multiple arguments from a packet, typically derived from the packet header, and including, for example, source and destination IP address, source and destination port numbers, and data protocol. These arguments are substantially independent of each other and describe different qualities of the packet. The TCAM holds classification rules that are triggered depending on particular argument values or ranges of values. The TCAM matches argument values of the packet to the argument values of the classification rules, and outputs that classification rule that represents the first match, normally including an action (e.g. accept or deny). The classification rules are placed in the TCAM in order of priority to naturally resolve situations where multiple classification rules may apply.
While TCAMS provide extremely fast packet classification, they have the disadvantage of high power consumption that scales proportionally to the number of search entries. A typical 18 megabit TCAM device can consume up to 15 watts of power when all of the entries are searched.